package Tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 *  题目 ：二叉树的前序遍历
 *  题目详述 ：
 *  给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
 *
 *  先序遍历，即存储顺序为 [父节点 ，左子节点 , 右子节点]
 */
public class PreorderTraversal {
    /**
     * 方法一 ：递归
     * @param root
     * @return
     */
    /*
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>(); // 用来存储结果集合
        // dfs方法所传递的参数，即（当前正在遍历的树节点 ， list结果集合）
        dfs(root , list);
        return list;
    }
    public void dfs(TreeNode node , List<Integer> list){
        if(node == null){
            return;
        }
        // 将当前遍历节点加入到结果集合（由于（1）其没有左子节点/（2）其左子节点已经加入到结果集合中）
        list.add(node.val);
        // 遍历左子树，直至左节点不存在为止；
        dfs(node.left , list);
        dfs(node.right , list);
    }
     */
    /**
     * 方法二 ：迭代
     * 类似与中序遍历（迭代），
     * 核心思想 ：即遍历整个二叉树，同时将父节点集合加入到栈中；
     *
     * 与中序遍历之间的区别 ：
     * （1）前序遍历 ：即，在于在将父节点加入到栈中时，同时也会将其加入到结果集合中；
     *  前序遍历的顺序 ：[根节点 ， 左子节点 ，右子节点]
     * （2）中序遍历 ：即，在与在将父节点弹出栈中时，捅死将其加入到结果集合中；
     * 中序遍历的顺序 ：[左子节点 ， 根节点 ， 右子节点]
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>(); // 栈顶用来存放当前遍历节点的父节点
        TreeNode node = root; // 使用node节点，来指向root根节点
        while( node != null || !stack.isEmpty()){
            // 循环结束条件： （1）栈为空 | （2）node == null ，
            // 以上两个条件同时满足，即代表遍历完了所有元素，同时对于其进行了中序遍历；
            while( node != null){
                result.add(node.val);
                // 当前遍历的节点不为空的话，即需要将当前节点压入栈中，同时使得node指向当前遍历节点的左子节点
                stack.push(node);
                node = node.left;
            }
            // 若是当前节点为空，则需要将当前栈顶元素弹出（即，其指向当前节点的父节点）
            TreeNode popNode = stack.pop();
            // 节点指向弹出节点（当前遍历节点的父节点）的右子节点
            node = popNode.right;
        }
        return result;
    }
}
